\chapter{Дискретная задача моментов}

% Почему там везде в X k_1 - 1. Так надо? Проверить весь текст на соответствие в этом месте!!!
% Интересно, а почему мно-во достижимости не пусто?
% Почему в условии оптимальности стоит квадрат нормы? Зачем? В доказательствах используется без квадрата!!!...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Дискретный процесс управления --- часть I}
\subsection{Постановка задачи}

Рассмотрим задачу управления линейной дискретной системой:

\begin{gather}
	x(k+1) = Ax(k) + Bu(k) + f, 			\\
	x \in \real ^n, u \in \real, 				\notag \\
	A \in \real ^{n \times n}, B \in \real ^{n \times 1}, f \in \real ^n . 	\notag
\end{gather}
Наша цель --- найти управление, переводящее систему из состояния	$x(k_0) = x^0$  в состояние $x(k_1) = x^1$ $(k_0 < k_1)$.

% Тут написать, что u ниразу не одномерно, более того, не конечномерно. Вроде бы нигде не используем. Проверить!

Выпишем формулу Коши решения нашей дискретной системы:
\begin{equation*} 
	x(k_1) = X(k_1, k_0)x^0 + \sum^{k_1-1}_{k=k_0} X(k_1, k) \left[ Bu(k) + f \right] = x^1.  
\end{equation*}

%Тут может быть пояснение про матрицант, фунд матрицу или ссылка на лекцию, где это описано

\noindent Обозначим
\begin{equation*} 
	c = x^1 - X(k_1, k_0)x^0 - \sum^{k_1-1}_{k=k_0} X(k_1, k)f. 
\end{equation*}
Тогда исходная задача сводится к решению системы из $n$ уравнений с $k_1-k_0-1$ неизвестными $u(k)$ при всех $k$
\begin{equation} 
	\sum^{k_1-1}_{k=k_0} X(k_1, k)Bu(k) = c,	\label{momentsTask} 
\end{equation}
называемой {\it задачей моментов}.

%Может быть стоит об этом сразу написать в постановке задачи в начале лекции?
Мы хотим управлять нашей системой неким оптимальным образом. Будем рассматривать критерий вида
\begin{equation*} \sum^{k_1-1}_{k=k_0} |u(k)|^2 \to \min. \end{equation*}

Перепишем его в виде
\begin{equation} \norm{u}^2_E =  \sum^{k_1-1}_{k=k_0} |u(k)|^2 \leqslant \mu^2.	\label{controlCriteria} \end{equation}
Мы иногда будем пользоваться эквивалентным неравенством без квадратов
\begin{equation} \norm{u}_E \leq \mu. \end{equation}

Итак, наша задача --- найти наименьшее $\mu$, при котором \eqref{momentsTask} имеет решение, удовлетворяющее \eqref{controlCriteria}, и выписать это (эти?) решение.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Множество достижимости и его свойства}
Для решения поставленной задачи нам понадобится понятие множества достижимости.

\begin{df}
Будем называть \emph{множеством достижимости} для задачи \eqref{momentsTask}, \eqref{controlCriteria} следующее множество
\begin{equation} 
	\soa_{\mu}[k_1, k_0] = \set{c}{c = \sum^{k_1-1}_{k=k_0} X(k_1-1, k)Bu(k) \text{ и } % 		 
		\eqref{controlCriteria} } \label{setOfAttainability}
\end{equation}
\end{df}

%%Тут бы вставить пояснения какой у этого множества смысл итп
%%Сделать команду для равно с надписью df =)))

\begin{stm}
	$\soa_{\mu}[k_1, k_0] \in \conv \real ^n$ \textup{(}непустой выпуклый компакт в $\real ^n$\textup{)}.
\end{stm}

\begin{proof}

Докажем выпуклость, замкнутость, ограниченность.

\emph{Выпуклость}:
Пусть $c_1, c_2 \in \soa_{\mu}$, значит $\exists\, u_1(\cdot), u_2(\cdot)$, удовлетворяющие \eqref{controlCriteria}, $c_j = \sum^{k_1-1}_{k=k_0} X(k_1, k)Bu_j(k)$.

Рассмотрим точки отрезка $c = \lambda c_1 + (1 - \lambda) c_2$, $\lambda \in (0,1)$. Выпуклость равносильна выполнению включения $c \in  \soa_{\mu}$ для $\forall \lambda$.

Возьмём $u = \lambda u_1 + (1 - \lambda) u_2$. Легко заметить, что $c = \sum^{k_1-1}_{k=k_0} X(k_1, l)Bu(k)$, следовательно нам достаточно проверить, что для $u$ выполняется условие \eqref{controlCriteria}. Это следует из выпуклости евклидовой нормы (вследствие неравенства треугольника):

\begin{equation*} 
	\norm{u}_E = \norm{\lambda u_1 + (1 - \lambda) u_2} \leqslant %
	\lambda \norm{u_1} + (1 - \lambda) \norm{u_2} \leqslant %
	\lambda \mu + (1 - \lambda) \mu = \mu.
\end{equation*}

\emph{Ограниченность}:
В первом условии из определения множества достижимости перейдём к норме
\begin{equation*} \norm{c} = \norm{\sum^{k_1-1}_{k=k_0} X(k_1-1, k)Bu(k)}. \end{equation*}

Оценим норму суммы сверху суммой норм, воспользуемся соотношением $\norm{XBu} \leq \norm{XB}\norm{u}$ (также именуемое субмультипликативностью матричной нормы). Получили конечную сумму, $\norm{u}$ ограничена по требованию оптимальности \eqref{controlCriteria}, $\norm{XB}$ ограничена т.\,к. $XB$ --- фиксированная матрица. В силу указанной цепочки неравенств $\norm{c}$ ограничена.
\begin{equation*} 
	\norm{\sum^{k_1-1}_{k=k_0} X(k_1-1, k)Bu(k)} \leqslant \sum^{k_1-1}_{k=k_0} {\norm{X(k_1-1, k)Bu(k)}} \leqslant %
	\sum^{k_1-1}_{k=k_0} {\norm{XB}\norm{u}} \leqslant 	\sum^{k_1-1}_{k=k_0} {C_k \mu}.
\end{equation*}

\emph{Замкнутость}: 
Для любой фундаментальной последовательности $\{c_j\}$ из $\soa_{\mu}$ возьмём соответствующую последовательность $\{u_j\}$ (они существуют по определению множества достижимости). Все $u_j$ лежат в шаре по условию \eqref{controlCriteria}. В конечномерном пространстве шар является компактом. А значит существует подпоследовательность $u_{j_{m}} \rightarrow u$ из шара. Т.\,к. $u$ из шара (удовлетворяет условию \eqref{controlCriteria}), то $c = \sum^{k_1-1}_{k=k_0} X(k_1, k)Bu(k)$ будет лежать в множестве достижимости и будет пределом последовательности $\{c_j\}$. А это и есть замкнутость. 

\end{proof}

% Сделать ссылку на лекцию, где рассказывается про опорные функции!
То же самое утверждение о выпуклости можно доказать, используя аппарат опорных функций. Покажем это.

\begin{stm}
	$\soa_{\mu}[k_1, k_0] \in \conv \real ^n$ \textup{(}не пустой выпуклый компакт в $\real ^n$\textup{)}.
\end{stm}

\begin{proof}
Рассмотрим опорную функцию множества достижимости.
\begin{multline} 
	\sufu{l}{\soa_{\mu}[k_1, k_0]} = %
	\sup \limits_{c \in \soa_{\mu}[k_1, k_0]} \scalar{l}{c} = %
    \sup \limits_{u(k_0), \ldots , u(k_1-1)} \scalar{l}{\sum^{k_1-1}_{k=k_0} X(k_1-1, k)Bu(k)} = \\
    \sup \limits_{u(k_0), \ldots , u(k_1-1)} \sum^{k_1-1}_{k=k_0} \scalar{\underbrace{B^T X^T(k_1-1, k) l}_{\text{обозначим за $s(k,l)$}}}{u(k)} =%
    \sup \limits_{u(k_0), \ldots , u(k_1-1)} \sum^{k_1-1}_{k=k_0} \scalar{s(k,l)}{u(k)}.
\end{multline}

%Вот эта конструкция ниже не понятна мне до конца. Проверить домыслы.
Это можно записать в виде $ \sup \limits_{u(\cdot)} \scalar{s(\cdot, l)}{u(\cdot)}. $ Если $u(k)$ --- скаляр, то можно составить из него вектор $u(\cdot)$. Если это был вектор, то можно записать для всех $k$ его компоненты в один большой вектор $u(\cdot)$. Если же $u(k)$ --- элемент бесконечномерного пространства, то тоже можно как-то аккуратно сделать их него $u(\cdot)$. То есть вся наша теория верна для $u(k)$ любой размерности, но мы пишем все формулы для скаляра, как было указанно в постановке задачи.

Итак, 
\begin{equation*} 
	\sufu {l}{\soa_{\mu}[k_1, k_0]} = %
    \sup \limits_{u(\cdot)} \scalar{s(\cdot, l)}{u(\cdot)}.
\end{equation*}
% Сюда в $ $ напечатать неравенство КБШ!

%Далее воспользуемся неравенством Коши-Буняковского-Шварца. Равенство (а значит, и максимум) будет достигаться на векторе, сонаправленном с $s(\cdot,l)$. Также это можно интерпретировать, как принадлежность $u(\cdot)$ шару в пространстве размерности $k_1 - k_0$ \left(это следует условия оптимальности \eqref{controlCriteria}\right). Таким образом, $u(\cdot)$ будет оптимальным, если он сонаправлен с $s(\cdot,l)$ и по норме равен $\mu$.

%Может быть, в формуле должен быть модуль s ^2???
\begin{equation*} 
	u(\cdot) = \dfrac{\mu s(\cdot)}{\norm{s(\cdot)}}; \hspace{10pt} %
	u(k) = \mu \dfrac{s(k)}{\sqrt{ \sum^{k_1-1}_{k=k_0} s^2 (k)} }.
\end{equation*} 

%Ссылочку на теорему про опорные функции вставить бы, где утверждается, что это компакт...
Следовательно, максимум опорной функции достигается, а значит множество достижимости --- компакт.

Отметим, что если максимум достигается, то 
\begin{equation} 
	\sufu {l}{\soa_{\mu}[k_1, k_0]} = %
    \sum^{k_1-1}_{k=k_0} s(k) \mu  \dfrac{s(k)}{\sqrt{ \sum^{k_1-1}_{k=k_0} s^2 (k)}} = %
    \mu \sqrt{ \sum^{k_1-1}_{k=k_0} |s(k)|^2 }.
\end{equation}

\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Исследование разрешимости задачи моментов}

Вернёмся к решению нашей исходной задачи:
% слегка изменил --- не понравится, вернём --- Николай.

%%%%%%%%%%%%% было
% \begin{gather*}
% 	x(k+1) = Ax(k) + Bu(k) + f	\\
% 	\text{Управлением перевести систему из } x(k_0) = x^0 \text{ в } x(k_1) = x^1 \\
% 	\text{Так, чтобы при этом } \norm{u(\cdot)} \text{ была минимально возможной}.
% \end{gather*}

%%%%%%%%%%%%% стало
\begin{equation*}
	x(k+1) = Ax(k) + Bu(k) + f.
\end{equation*}
Управлением перевести систему из  $x(k_0) = x^0$ в $x(k_1) = x^1$ так, чтобы при этом $\norm{u(\cdot)}$ была минимально возможной.

Мы свели её к следующей задаче моментов (найти наименьшее $\mu$ и соответствующее управление):
\begin{gather*} 
	\sum^{k_1-1}_{k=k_0} X(k_1, k)Bu(k) = c, \\
    \norm{u}^2_E =  \sum^{k_1-1}_{k=k_0} |u(k)|^2 \leq \mu^2.
\end{gather*}

\begin{note}
	Следующие утверждения эквивалентны:
	\begin{itemize}	
		\item Пара $u(\cdot), \mu$ является решением задачи моментов;
		
		\item $c(u) \in \soa_{\mu}$ --- множеству достижимости;
		
		\item $\scalar{l}{c(u)} \leq \mu \sqrt{ \sum^{k_1-1}_{k=k_0} |s(k, l)|^2 } \hspace{5pt} \forall l.$
	\end{itemize}	
\end{note}

Из третьего пункта следует, что для решения задачи моментов нам нужно найти наименьшее $\mu$, при котором выполняется соотношение:
\begin{equation} 
	\mu \geqslant \mu _0 = \sup \limits_{l \ne 0} \dfrac{\scalar{l}{c}}{\sqrt{ \sum^{k_1-1}_{k=k_0} |s(k, l)|^2}  } \label{muInequality}.
\end{equation} 
То же самое можно записать так:
\begin{gather*} 
	\mu _0 = \left\{ \sup \scalar{l}{c} \middle| \sum^{k_1-1}_{k=k_0} |s(k, l)|^2 = 1 \right\} %
	\text{ или, что то же, } %
    \dfrac{1}{\mu _0} = \inf \left\{ \sqrt{ \sum^{k_1-1}_{k=k_0} |s(k, l)|^2} \middle| \scalar{l}{c} = 1 \right\}.
\end{gather*} 
Заметим, что $\mu _0$ может быть равным $+\infty$ даже при условии $l \ne 0$ (все $s$ могут стать равными нулю). В таком случае задача моментов не будет иметь решения (не существует требуемых $\mu$). 

Получается, что задача моментов не разрешима, когда 
\begin{equation*} 
	\sum^{k_1-1}_{k=k_0} |s(k, l)|^2 = 0.
\end{equation*} 
Рассмотрим все такие $l$, при которых выполняется равенство, т.\,е. рассмотрим
\begin{equation*} 
	l \text{ т.\,ч. } \forall k |s(k, l)| = 0.
\end{equation*}
Это эквивалентно включению
\begin{equation*} 
	l \in \bigcap\limits^{k_1-1}_{k=k_0} \ker B^T X^T (k_1-1, k),
\end{equation*}
так как $s(k, l) = B^T X^T (k_1-1, k) l$ и для равенства нулю всех $k$ требуется принадлежность $l$ ядрам при всех $k$.

Пересечение ядер является линейным подпространством (так как каждое из них является линейным подпространством). Возможны два случая:
\begin{enumerate}
	\item Это подпространство тривиально $\Rightarrow \sup$ в \eqref{muInequality} конечен, $\mu$ существует $\Rightarrow$ задача моментов разрешима.
	% Почему???
	\item Оно нетривиально. Тогда требуется, чтобы $c$ было ортогонально этому пересечению ядер для конечности супремума.
\end{enumerate}

Если 
\begin{equation*} 
	c \not\perp \bigcap\limits^{k_1-1}_{k=k_0} \ker B^T X^T (k_1-1, k),
\end{equation*}
то возьмём $l$ из пересечения ядер. Что-то сделаем с каким-то неравенством. Там что-то занулится, а что-то нет. Оно не получается, значит $c \not\in \soa_{\mu}[k_1, k_0] \forall \mu$. Задача моментов не разрешима.
%% ЧТО ЗА НЕРАВЕНСТВО ИМЕННО?
% FIXME: прояснить момент

Пусть
\begin{equation*} 
	c \perp \bigcap\limits^{k_1-1}_{k=k_0} \ker B^T X^T (k_1-1, k).
\end{equation*}
В этом случае в неравенстве если правая часть ноль, то и левая ноль. Задача моментов разрешима. Интересно, когда правая часть не ноль (подпространство).

% В чём смысл этой записи?
\begin{equation*} 
	\bigcap\limits^{k_1-1}_{k=k_0} \ker B^T X^T (k_1-1, k) = %
	\left\{ \left( \underbrace{0, \ldots, 0}_p, x_{p+1}, \ldots, x_n \right) \right\}
\end{equation*}
Тогда для супремума
\begin{equation*} 
	\sup \limits_{l \ne 0} \dfrac{\scalar{l}{c}}{\sqrt{ \sum^{k_1-1}_{k=k_0} |s(k, l)|^2}  }
\end{equation*}
достаточно рассмотреть $l$, у которых $x_{p+1}, \ldots, x_n = 0$.
\begin{equation*} 
	\sup \limits_{(l_1 \ldots l_p) \neq 0} \dfrac{\sum\limits_{j=1}^p l_j c_j} {\sqrt{ \sum^{k_1-1}_{k=k_0} |s(k, l)|^2}}.
\end{equation*}
Тогда знаменатель не равен нулю, супремум достигается, можно брать его по $(l_1 \ldots l_p) \neq 0, \sum\limits_{j=1}^p l_j = 1$.


%Далее по лекциям Данилы до геометрической интерпретации...

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Геометрический	смысл (отступление)}
% Точно ли случай с не перпендикулярен пересечению ядер даёт 100% неразрешимость? Или просто нет достаточности?
Посмотрим на выкладки с геометрической точки зрения. С учётом вышесказанного, для разрешимости задачи моментов (а значит принадлежности $c$ множеству достижимости) ?необходимо? и достаточно, чтобы $c$ было ортогонально пересечению ядер, если это пересечение нетривиально, и любым, если оно тривиально. Следовательно:
\begin{equation*} 
	\soa_{\mu}[k_1, k_0] \subseteq \left( \bigcap\limits^{k_1-1}_{k=k_0} \ker B^T X^T (k_1-1, k) \right) ^{\perp}.
\end{equation*}

%%% TODO: Тут бы рисуночек от Месяца нарисовать и вставить...

И при $\forall \mu$ множество достижимости будет находится в этом ортогональном дополнении. И для $\forall c \in (\cap \ker (\ldots))^{\perp}$ найдётся $\mu$, что $\soa_{\mu}[k_1, k_0]$ обхватит $c$. При этом 
\begin{equation*} 
	\lim\limits_{\mu \rightarrow \infty} \soa_{\mu}[k_1, k_0] = (\cap \ker (\ldots))^{\perp}.
\end{equation*}

% Чот тут относительная внутренность это вроде относительно аффинной оболочки... - там точно так пишется?
Также оказывается, что $(\cap \ker (\ldots))^{\perp}$ --- такая гиперплоскость, относительная внутренность $\soa_{\mu}[k_1, k_0]$ относительно которой не пуста.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Решение задачи моментов}
Итак, мы нашли $\mu_0$. Осталось найти управление. Для этого найдём, на каком именно $l_0$ достигается супремум
\begin{equation*} 
	\mu _0 = \left\{ \sup \scalar{l}{c} \middle| \sum^{k_1-1}_{k=k_0} |s(k, l)|^2 = 1 \right\}.
\end{equation*}

\begin{equation*} 
	\sum^{k_1-1}_{k=k_0} |s(k, l)|^2 = 1 \Leftrightarrow \sum^{k_1-1}_{k=k_0} |B^T X^T(k_1-1, k)l|^2 = 1.
\end{equation*}
Если ядро нетривиально, то это эллипсоид. Если ядро тривиально --- эллипсоидальный цилиндр.

%% ТУТ БУДЕТ ПОЯСНЕНИЕ И ССЫЛКИ?

Итак, в выражении для $\mu_0$ можно брать $\sup$ по $M^{\perp}$ --- эллипсоид в сечении ограничен $\Rightarrow$ супремум достигается.

%%% Тут ещё будет текст и выписано управление от l_0, только вот непонятно, откуда мы вытащили l_0 мне пока.